package arithmetic1.tree.avlTree;

/*
    平衡二叉树:
        将二叉排序树转换为平衡二叉树的方法：
            左旋(rightHeight-leftHeight>1):
                1.创建一个值和当前根节点一样的新节点
                2.把新节点的左子树设置为当前节点的左子树
                3.把新节点的右子树设置为当前节点的右子树的左子树
                4.把当前节点的值变为当前节点右子节点的值
                5.把当前节点的右子节点设置为右子节点的右子节点
                6.把当前节点的左子节点设置为新节点
            右旋(leftHeight-rightHeight>1):
                1.创建一个值和当前节点一样的新节点
                2.把新节点的右子节点设置为当前节点的右子节点
                3.把新节点的左子节点设置为当前节点的左子节点的右子节点
                4.把当前节点的值变为当前节点左子节点的值
                5.把当前节点的左子节点设置为当前节点的左子节点的左子节点
                6.把当前节点的右子节点设置为新节点
            双旋:
                当符合左旋条件时，如果当前根节点的右子节点的左子树高度大于右子树高度，应该先对右子节点进行右旋，再对当前根节点左旋
                当符合右旋条件时，如果当前根节点的左子节点的右子树高度大于左子树高度，应该先对左子节点进行左旋，再对当前根节点右旋
 */
public class AVLBinaryTree {
    private Node root;

    public AVLBinaryTree() {
    }

    public AVLBinaryTree(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }

    //添加一个节点，并且自动调整为平衡二叉树,flag为true代表需要判断是否旋转
    public void addNode(Node root,Node node,boolean flag){
        if(root!=null){ //树不为空
            if(node.data<root.data){ //该节点小于根节点的值
                //将其放在左边
                if(root.leftNode==null){
                    root.leftNode=node;
                }else {
                    addNode(root.leftNode,node,false);
                }
            }else { //该节点大于等于根节点的值
                //将其放在右边
                if(root.rightNode==null){
                    root.rightNode=node;
                }else {
                    addNode(root.rightNode,node,false);
                }
            }
        }else { //树为空时
            this.root=node;
        }
        if(flag){
            //添加完时判断该二叉树是否需要旋转
            if(rightHeight(getRoot())-leftHeight(getRoot())>1){   //需要左旋
                if(leftHeight(getRoot().rightNode)>rightHeight(getRoot().rightNode)){   //当前根节点的右子节点的左子树高度大于右子树高度,需要双旋
                    //对右子节点进行右旋
                    rightRotate(getRoot().rightNode);
                    //再对当前根节点左旋
                    leftRotate(getRoot());
                }else{  //直接左旋
                    leftRotate(getRoot());
                }
            }else if(leftHeight(getRoot())-rightHeight(getRoot())>1){ //需要右旋
                if(rightHeight(getRoot().leftNode)>leftHeight(getRoot().leftNode)){   //当前根节点的左子节点的右子树高度大于左子树高度,需要双旋
                    //对左子节点进行左旋
                    leftRotate(getRoot().leftNode);
                    //再对当前根节点右旋
                    rightRotate(getRoot());
                }else{  //直接右旋
                    rightRotate(getRoot());
                }
            }
        }
    }

    //将一个数组创建成二叉排序树
    public void createTree(int arr[]){
        for(int i=0;i<arr.length;i++){
            addNode(root,new Node(arr[i]),true);
        }
    }

    //求以当前节点为根节点的树的高度
    public int treeHeight(Node root){
        if(root==null){
            return 0;
        }
        return Math.max(root.leftNode!=null?treeHeight(root.leftNode):0,root.rightNode!=null?treeHeight(root.rightNode):0)+1;
    }

    //求以当前节点为根节点的左子树高度，
    public int leftHeight(Node root){
        return treeHeight(root.leftNode);
    }

    //求以当前节点为根节点的右子树高度，
    public int rightHeight(Node root){
        return treeHeight(root.rightNode);
    }

    //将以当前节点为根节点的树左旋
    public void leftRotate(Node root){
        //1.创建一个值和当前根节点一样的新节点
        Node newNode=new Node(root.data);
        //2.把新节点的左子树设置为当前节点的左子树
        newNode.leftNode=root.leftNode;
        //3.把新节点的右子树设置为当前节点的右子树的左子树
        newNode.rightNode=root.rightNode.leftNode;
        //4.把当前节点的值变为当前节点右子节点的值
        root.data=root.rightNode.data;
        //5.把当前节点的右子节点设置为右子节点的右子节点
        root.rightNode=root.rightNode.rightNode;
        //6.把当前节点的左子节点设置为新节点
        root.leftNode=newNode;
    }

    //将以当前节点为根节点的树右旋
    public void rightRotate(Node root){
        //1.创建一个值和当前节点一样的新节点
        Node newNode=new Node(root.data);
        //2.把新节点的右子节点设置为当前节点的右子节点
        newNode.rightNode=root.rightNode;
        //3.把新节点的左子节点设置为当前节点的左子节点的右子节点
        newNode.leftNode=root.leftNode.rightNode;
        //4.把当前节点的值变为当前节点左子节点的值
        root.data=root.leftNode.data;
        //5.把当前节点的左子节点设置为当前节点的左子节点的左子节点
        root.leftNode=root.leftNode.leftNode;
        //6.把当前节点的右子节点设置为新节点
        root.rightNode=newNode;
    }


    //删除一个节点  flag为true代表parent指针需要移动，key为0代表parent下一步需要向左移动，为1下一步需要向右移动
    public void removeNode(Node root,Node parent,boolean flag,int key,int target){
        if(root!=null){ //树不为空
            if(root.data==target){  //删除的是根节点
                if(root.leftNode==null && root.rightNode==null){    //该节点为叶子节点
                    if(parent.leftNode!=null && parent.leftNode.data==target){   //该节点是parent的左子节点
                        parent.leftNode=null;
                    }else{  //该节点是parent的右子节点
                        parent.rightNode=null;
                    }
                }else if(root.leftNode==null && root.rightNode!=null){   //该节点只有右子节点
                    if(parent==root){   //删除的是根节点
                        root.data=root.rightNode.data;
                        root.rightNode=null;
                    }else {
                        if(parent.leftNode.data==target){  //该节点是parent的左子节点
                            parent.leftNode=root.rightNode;
                        }else {     //该节点是parent的右子节点
                            parent.rightNode=root.rightNode;
                        }
                    }
                }else if(root.leftNode!=null && root.rightNode==null){  //该节点只有左子节点
                    if(parent==root){   //删除的是根节点
                        root.data=root.leftNode.data;
                        root.leftNode=null;
                    }else {
                        if(parent.leftNode.data==target){   //该节点是parent的左子节点
                            parent.leftNode=root.leftNode;
                        }else{  //该节点是parent的右子节点
                            parent.rightNode=root.leftNode;
                        }
                    }
                }else { //该节点有两个子节点
                    //将该节点右子树上的最小的节点放到该节点的位置
                    int data;   //用来保存最小的节点的值
                    Node temp=root; //指针来指向最小的节点的父节点
                    if(temp.rightNode.leftNode==null){  //该节点的右子节点是最小的节点
                        data=temp.rightNode.data;
                        temp.rightNode=null;
                        root.data=data;
                    }else {     //该节点的右子节点不是最小的
                        temp=temp.rightNode;
                        while(temp.leftNode.leftNode!=null){
                            temp=temp.leftNode;
                        }
                        //保存最小的值
                        data=temp.leftNode.data;
                        //删除最小的节点
                        temp.leftNode=null;
                        root.data=data;
                    }
                }
            }else if(root.data<target){ //目标节点大于根节点
                //向右继续寻找
                if(flag){   //parent需要移动
                    if(key==0){ //向左移动
                        removeNode(root.rightNode,parent.leftNode,true,0,target);
                    }else { //向右移动
                        removeNode(root.rightNode,parent.rightNode,true,1,target);
                    }
                }else { //parent不需要移动
                    removeNode(root.rightNode,parent,true,1,target);
                }
            }else { //目标节点小于根节点
                //向左继续寻找
                if(flag){   //parent需要移动
                    if(key==0){     //向左移动
                        removeNode(root.leftNode,parent.leftNode,true,0,target);
                    }else {   //向右移动
                        removeNode(root.leftNode,parent.rightNode,true,1,target);
                    }
                }else {    //parent不需要移动
                    removeNode(root.leftNode,parent,true,0,target);
                }
            }
        }
    }
    public void removeNode(int target){
        removeNode(this.root,this.root,false,0,target);
    }

    //先序遍历
    public void preOrder(Node root){
        if(root!=null){
            System.out.print(root+"\t");
            if(root.leftNode!=null){
                preOrder(root.leftNode);
            }
            if(root.rightNode!=null){
                preOrder(root.rightNode);
            }
        }
    }
    public void preOrder(){
        preOrder(root);
    }
}

class Node{
    int data;
    Node leftNode;
    Node rightNode;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
        this.leftNode=null;
        this.rightNode=null;
    }

    @Override
    public String toString() {
        return data+"";
    }
}

class Test{
    public static void main(String[] args) {
//        int arr[]={7,3,10,5,1,9,12,11,4};
//        int arr[]={7,3,10,8,11,12}; //需要左旋
//        int arr[]={10,9,12,7,6};  //需要右旋
        int arr[]={10,5,12,4,6,7};
        AVLBinaryTree avlBinaryTree=new AVLBinaryTree();
        avlBinaryTree.createTree(arr);
        avlBinaryTree.preOrder();

        System.out.println();
        int height=avlBinaryTree.treeHeight(avlBinaryTree.getRoot());
        System.out.println("树的高度:"+height);
    }
}
